package main

import (
	"context"
	"fmt"
	"io"
	"log"
	"math"
	"net/http"
	"sort"
	"sync"
)

func main() {
	// Q1:
	nums := []int{3, 5, 3, 6, 6, 2, 5, 9}
	target := 8
	log.Print(findSub(nums, target))
	// Q2:
	S := "ADOBECODEBANC"
	T := "ABC"
	log.Print(minWindow(S, T))

	// think1:
	S1 := "ADOBECODEABC"
	T1 := "ABCD"
	if res, ok := minWindow1(S1, T1); ok {
		log.Print(S1[res[0] : res[1]+1])
	}
}

func minWindow1(s string, t string) ([]int, bool) {
	var res []int
	start := 0
	tL := len(t)
	for i := start; i < len(s); i++ {
		if start == tL {
			return res, true
		}
		if t[start] == s[i] {
			if start == 0 || start == tL-1 {
				res = append(res, i)
			}
			start++
			continue
		}
		res = []int{}
		start = 0
	}
	return res, false
}

func findSub(nums []int, target int) [][]int {
	var (
		res  [][]int
		path []int
	)
	sort.Ints(nums)
	backTrack(nums, target, 0, path, &res)
	return res
}
func backTrack(nums []int, target int, start int, path []int, res *[][]int) {
	//if target == 0 {
	//	*res = append(*res, path)
	//	return
	//}
	for i := start; i < len(nums); i++ {
		if i > start && nums[i] == nums[i-1] {
			continue
		}
		if nums[i] > target {
			break
		}
		path = append(path, nums[i])
		backTrack(nums, target-nums[i], i+1, path, res)
		path = path[:len(path)-1]
	}
	if target == 0 {
		*res = append(*res, path)
		return
	}
}
func subjects(nums []int, target int) [][]int {
	var (
		res  [][]int
		path []int
	)
	var backTrack func(int, []int, int)
	backTrack = func(start int, path []int, target int) {
		for i := start; i < len(nums); i++ {
			if i > start && nums[i] == nums[i-1] {
				continue
			}
			if nums[i] > target {
				break
			}
			path = append(path, nums[i])
			backTrack(i+1, path, target-nums[i])
			path = path[:len(path)-1]
		}
		//if target == 0 {
		res = append(res, path)
		//}
	}
	backTrack(0, path, target)
	return res
}

func minWindow(S string, T string) string {
	if len(S) == 0 || len(T) == 0 {
		return ""
	}

	tCount := make(map[rune]int, len(T))
	for _, ch := range T {
		tCount[ch]++
	}

	sCount := make(map[rune]int)
	required := len(tCount)
	// 当前窗口中满足条件的字符数量
	formed := 0

	l, r := 0, 0
	minLen := math.MaxInt32
	start := 0

	for r < len(S) {
		// 扩展窗口
		ch := rune(S[r])
		sCount[ch]++
		if tCount[ch] > 0 && sCount[ch] == tCount[ch] {
			formed++
		}
		r++

		// 收缩窗口
		for l <= r && formed == required {
			if r-l < minLen {
				minLen = r - l
				start = l
			}
			ch = rune(S[l])
			sCount[ch]--
			if tCount[ch] > 0 && sCount[ch] < tCount[ch] {
				formed--
			}
			l++
		}
	}

	if minLen == math.MaxInt32 {
		return ""
	}
	return S[start : start+minLen]
}

func fetch(ctx context.Context, wg *sync.WaitGroup, url string, ch chan<- string) {
	defer wg.Done()

	// 使用 select 监听上下文的取消
	req, err := http.NewRequestWithContext(ctx, "GET", url, nil)
	if err != nil {
		fmt.Printf("Failed to create request: %v\n", err)
		return
	}

	resp, err := http.DefaultClient.Do(req)
	if err != nil {
		fmt.Printf("Failed to fetch %s: %v\n", url, err)
		return
	}
	defer resp.Body.Close()

	body, err := io.ReadAll(resp.Body)
	if err != nil {
		fmt.Printf("Failed to read response from %s: %v\n", url, err)
		return
	}

	select {
	case <-ctx.Done():
		// 如果上下文已经取消，则直接退出
		return
	default:
		ch <- string(body)
	}
}
func concurrentFetch() {
	// 创建一个带有取消功能的上下文
	ctx, cancel := context.WithCancel(context.Background())
	defer cancel()

	var wg sync.WaitGroup
	ch := make(chan string)

	urls := []string{
		"https://example.com",
		"https://example.org",
		"https://example.net",
	}

	// 启动并发抓取
	for _, url := range urls {
		wg.Add(1)
		go fetch(ctx, &wg, url, ch)
	}

	// 等待其中一个抓取完成
	go func() {
		content := <-ch
		fmt.Println("Fetched content from one of the URLs:")
		fmt.Println(content)

		// 取消上下文以通知其他 goroutine 退出
		cancel()
	}()

	// 等待所有的抓取操作结束
	wg.Wait()
	fmt.Println("Program exited.")
}
